#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <sys/time.h>

using namespace std;

long long uniquePaths(int m, int n) 
{
  long long ret=0;
  if( (m+n) < 2 )
    return ret;
  const int lenm=m+1;
  const int lenn=n+1;
  long long up[lenm][lenn];
  for(int i=0;i<lenm;i++)
  {
    memset( up[i], 0, lenn*sizeof(long  long) );
  }

  up[0][1] = 1;
  for(int i=1;i<=m;++i)
  {
    for(int j=1;j<=n;++j)
    {
      up[i][j] = up[i-1][j] + up[i][j-1];
    }
  }

  ret = up[m][n];

  return ret;
}



int main(int argc,char *argv[])
{

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  cout<<"m,n:10,10:"<<uniquePaths(10,10)<<endl;
  cout<<"m,n:100,100:"<<uniquePaths(100,100)<<endl;

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;



  return 0;
}
